const COINS: [usize; 8] = [1, 2, 5, 10, 20, 30, 50, 100];

pub fn dp_rec_mc(amount: u32) -> u32 {
    let amount = amount as usize;
    let mut memo = vec![u32::MAX; amount + 1];
    // base case
    memo[0] = 0;
    for i in 1..=amount {
        let mut min = std::u32::MAX;
        COINS
            .iter()
            .filter(|&x| i >= *x && memo[i - *x] != std::u32::MAX)
            .for_each(|&x| {
                min = min.min(memo[i - x] + 1);
            });
        memo[i] = min;
    }
    memo[amount as usize]
}
